package trietree

func NewTrieTree() *TrieTree {
	// 仅用于英文
	return &TrieTree{root: &Node{pass:0, end:0, next: make([]*Node, 26)}}
}

type TrieTree struct {
	root *Node
}

type Node struct {
	pass int
	end int
	next []*Node
	// next map[string]*Node 数据比较复杂的时候，使用该结构
}

func (t *TrieTree) Insert(str string) {
	if str == "" {  // 防止空字符进入
		return
	}
	cur := t.root  // 从根节点出发
	cur.pass++     // 加入的字符一定不为空，根节点经过的路径一定加一
	var path int   // 表示路径
	for _, v := range str { // 遍历路径
		path = int(v-'a') // 计算实际的路径
		if cur.next[path] == nil { // 不存在路径则创建节点
			cur.next[path] = &Node{pass:0, end:0, next: make([]*Node, 26)}
		}
		cur = cur.next[path] // 走过当前路径
		cur.pass++           // 走过的路径的pass+1
	}
	cur.end++
}

func (t *TrieTree) Search(str string) int {
	cur := t.root // 从根节点出发
	for _, v := range str {
		if cur.next[v-'a'] == nil { // 不存在路径时直接返回 0 个
			return 0
		}
		cur = cur.next[v-'a']
	}
	return cur.end // 返回经过路径的结束数量
}

func (t *TrieTree) Delete(str string) {
	if t.Search(str) != 0 { // 存在该节点时才需要删除
		cur := t.root
		for _, v := range str {
			if cur.next[v-'a'].pass == 1 { // 该路径后续之后唯一一条路径时，直接将整条路径删除, 并返回
				cur.next[v-'a'] = nil
				return
			}
			cur = cur.next[v-'a']
			cur.pass--
		}
		cur.end--
	}
}

func (t *TrieTree) Prefix(str string) int {
	if str == "" {
		return 0
	}
	cur := t.root
	for _, v := range str {
		if cur.next[v -'a'] == nil {
			return 0
		}
		cur = cur.next[v -'a']
	}
	return cur.pass
}





